#ifndef GRAPH_H
#define GRAPH_H

// From stackoverflow.com/questions/671714,
// by Gregor Fabritius:

#include <boost/graph/adjacency_list.hpp>
#include <boost/unordered_map.hpp>

#include "Parser.h"
#include <iostream>
#include "Log.h"

using namespace boost;


/* definition of basic boost::graph properties */
enum vertex_properties_t { vertex_properties };
enum edge_properties_t   { edge_properties };
namespace boost {
    BOOST_INSTALL_PROPERTY(vertex, properties);
    BOOST_INSTALL_PROPERTY(edge, properties);
}

// the graph base class template
// VP: Vertex Property
// EP: Edge Property
// VN: Vertex Name (usually an int)
template < typename VP, typename EP, typename VN >
class Graph {
public:
    // the adjacency_list which stores the connectivity information
    typedef adjacency_list<vecS,
                           vecS,
                           directedS,
                           property<vertex_properties_t, VP,
                                    property<vertex_name_t, VN>
                                    >,
                           property<edge_properties_t, EP>
                           > graph_t;

    // subtypes of this class, for accessing parts of it.
    typedef typename graph_traits<graph_t>::vertex_descriptor
    vertex_t;

    typedef typename graph_traits<graph_t>::edge_descriptor
    edge_t;

    typedef typename graph_traits<graph_t>::vertex_iterator
    vertex_iter_t;

    typedef typename graph_traits<graph_t>::edge_iterator
    edge_iter_t;

    typedef typename graph_traits<graph_t>::adjacency_iterator
    adjacency_iter_t;

    typedef typename graph_traits<graph_t>::out_edge_iterator
    out_edge_iter_t;

    typedef typename graph_traits<graph_t>::degree_size_type
    degree_t;

    typedef std::pair<adjacency_iter_t, adjacency_iter_t>
    adjacency_vertex_range_t;

    typedef std::pair<out_edge_iter_t, out_edge_iter_t>
    out_edge_range_t;

    typedef std::pair<vertex_iter_t, vertex_iter_t>
    vertex_range_t;

    typedef std::pair<edge_iter_t, edge_iter_t>
    edge_range_t;

    typedef typename property_map<graph_t, vertex_properties_t>::type
    vertex_property_map_t;

    typedef typename property_map<graph_t, edge_properties_t>::type
    edge_property_map_t;

    typedef typename property_map<graph_t, vertex_name_t>::type
    vertex_name_property_map_t;

    // Constructors and destructor
    Graph() {
    }

    // Operators
    Graph& operator=(const Graph &rhs) {
        LOG_ENTER(GRAPH, "Graph::operator=");

        graph = rhs.graph;

        LOG_EXIT();

        return *this;
    }

    // copy constructor.  Build a fresh graph
//    Graph(const Graph& g) : Graph(g.graph) {
    Graph(const Graph& g) {
        LOG_ENTER(GRAPH, "Graph::copy constructor!");

        vertex_range_t v_iters = get_vertices();
        vertex_iter_t v_iter = v_iters.first;
        vertex_iter_t v_end  = v_iters.second;
        for (; v_iter != v_end; v_iter++) {
            VP& vp = properties(*v_iter);
            VN vn = get_vertex_name(*v_iter);
            add_vertex(vp, vn);
        }

        edge_range_t e_iters = get_edges();
        edge_iter_t e_iter = e_iters.first;
        edge_iter_t e_end  = e_iters.second;
        for (; e_iter != e_end; e_iter++) {
            const vertex_t src = source(*e_iter, graph);
            const vertex_t dst = target(*e_iter, graph);
            VN srcID = get_vertex_name(src);
            VN& dstID = get_vertex_name(dst);
            EP& ep = properties(*e_iter);
            add_edge(srcID, dstID, ep);
        }

        LOG_EXIT();
    }

    virtual ~Graph() {
    }

    // modifying methods
    void clear() {
        graph.clear();
        vertex_from_name.clear();
        name_from_vertex.clear();
    }

    vertex_t add_vertex(const VP& prop, const VN& name) {
        const vertex_t v = boost::add_vertex(graph);
        properties(v)   = prop;
        // name_from_vertex[v] = name;
        // vertex_from_name[name] = v;
        set_vertex_name(v, name);
        return v;
    }

    void remove_vertex(const vertex_t& v) {
        VN name = get_vertex_name(v);
        vertex_from_name.erase(name);
        name_from_vertex.erase(vertex);

        clear_vertex(v, graph);
        boost::remove_vertex(v, graph);
    }

    edge_t add_edge(const VN& name1,
                    const VN& name2,
                    const EP& prop) {
        vertex_t v1 = vertex_from_name[name1];
        vertex_t v2 = vertex_from_name[name2];
        return add_edge(v1,v2, prop);
    }

    edge_t add_edge(const vertex_t& v1,
                    const vertex_t& v2,
                    const EP& prop) {
        edge_t added_edge = boost::add_edge(v1, v2, graph).first;
        properties(added_edge) = prop;

        return added_edge;
    }

    // property accessors

    // vertex: LHS
    VP& properties(const vertex_t& v) {
        vertex_property_map_t param = get(vertex_properties, graph);
        return param[v];
    }

    // vertex properties: RHS
    const VP& properties(const vertex_t& v) const {

        LOG_ENTER(GRAPH, "Graph::properties");
        LOG(GRAPH) << "v = " << v;

        vertex_property_map_t param = get(vertex_properties, graph);

        LOG_EXIT();

        return param[v];
    }

    // vertex name: RHS
    VN get_vertex_name(const vertex_t v) const {
        LOG(GRAPH) << "Graph::get_vertex_name";

        LOG_EXIT();

        return name_from_vertex.at(v);
    }

    // vertex name: LHS
    void set_vertex_name(const vertex_t& v, const VN& name) {

        LOG_ENTER(GRAPH, "Graph::set_vertex_name");
        LOG(GRAPH) << " v=" << v << " name=" << name;

        name_from_vertex.insert(std::make_pair(v, name));
        vertex_from_name.insert(std::make_pair(name, v));

        LOG(GRAPH) << "after insert, stored name=" << name_from_vertex.at(v);
        LOG(GRAPH) << "after insert, stored vert=" << vertex_from_name.at(v);

        // name_from_vertex[v] = name;
        // vertex_from_name[name] = v;

        LOG_EXIT();
    }

    // edge: LHS
    EP& properties(const edge_t& v){
        edge_property_map_t param = get(edge_properties, graph);
        return param[v];
    }

    // edge: RHS
    const EP& properties(const edge_t& v) const {
        edge_property_map_t param = get(edge_properties, graph);
        return param[v];
    }

    // access to the container, and to its parts
    const graph_t& get_graph() const {
        return graph;
    }

    vertex_range_t get_vertices() const {
        return vertices(graph);
    }

    edge_range_t get_edges() const {
        return edges(graph);
    }

    adjacency_vertex_range_t get_adjacent_vertices(const vertex_t& v) const {
        return adjacent_vertices(v, graph);
    }

    int get_vertex_count() const {
        return num_vertices(graph);
    }

    int get_edge_count() const {
        return num_edges(graph);
    }

    int get_vertex_degree(const vertex_t& v) const {
        return out_degree(v, graph);
    }

    vertex_t get_vertex(const VN& name) {
        return vertex_from_name[name];
    }

    vertex_t get_source(const edge_t& e) {
        vertex_t result = source(e, graph);
        return result;
    }

    vertex_t get_target(const edge_t& e) {
        return target(e, graph);
    }

    std::ostream& print(std::ostream& os) {
        LOG_ENTER(GRAPH, "Graph::print");
        LOG(GRAPH) << " this=" << (void*)this;

        vertex_range_t v_iters = get_vertices();
        vertex_iter_t v_iter = v_iters.first;
        vertex_iter_t v_end  = v_iters.second;

        LOG(GRAPH) << "v_iter = " << *v_iter;
        LOG(GRAPH) << "v_end = " << (void*)&v_end;

        for (; v_iter != v_end; v_iter++) {

//            LOG(GRAPH) << "*v_iter = " << *v_iter;

            VP& vp = properties(*v_iter);
            VN vn = get_vertex_name(*v_iter);
            os
                << vn << " "
                << vp << "\n";

            // adjacency_vertex_range_t r = get_adjacent_vertices(*v_iter);
            // adjacency_iter_t iter     = r.first;
            // adjacency_iter_t iter_end = r.second;

            // for (; iter != iter_end; iter++) {
            //     VN neighbor_name = get_vertex_name(*iter);
            //     os << " > " << neighbor_name;
            // }
            // os << "\n";
        }

        LOG(GRAPH) << "  printed all the verts";

        edge_range_t e_iters = get_edges();
        edge_iter_t e_iter = e_iters.first;
        edge_iter_t e_end  = e_iters.second;
        for (; e_iter != e_end; e_iter++) {
            const vertex_t src = source(*e_iter, graph);
            const vertex_t dst = target(*e_iter, graph);
            VP& svp = properties(src);
            VP& dvp = properties(dst);
            VN srcID = get_vertex_name(src);
            VN dstID = get_vertex_name(dst);
            EP& ep = properties(*e_iter);
            os
                << srcID << " > " << dstID << " "
                << ep << "\n";
        }

        LOG(GRAPH) << "  printed all the edges";

        LOG_EXIT();

        return os;
    }

    std::istream& read(std::istream& is) {
        std::string text_line;
        while (!is.eof()) {
            std::getline(is, text_line);
            Parser p(text_line);

            VN src_name;
            VN dst_name;
            vertex_t src;
            vertex_t dst;
            VP vertex_property;
            EP edge_property;

            if (p.done()) { // empty input line
                continue;
            }

            else if (match_vertex(p, src_name, vertex_property)) {
                add_vertex(vertex_property, src_name);
            }
            else if (match_edge(p, src_name, dst_name, edge_property)) {
                vertex_t src = vertex_from_name[src_name];
                vertex_t dst = vertex_from_name[dst_name];
                add_edge(src, dst, edge_property);
            }
            else {
                throw std::string("malformed data line: " + text_line);
            }
        }
        return is;
    }

private:
    bool match_vertex(Parser& parser, VN& vn, VP& vp) {
        // Cases:
        // a: 10              lone vertex
        // b: 10 > 20         edge
        // c: 10 [1 2 3 4 5]  vertex with property
        int m = 0;

        if ((m = parser.match_int (vn)) != 1) {
            parser.backup(1); // weird invalid non-vertex, non-edge line
            return false;
        }

        if (parser.done()) { // case a
            return false;
        }

        if (parser.match_char("[") == 1) {// case c
            parser.backup(m); // undo bracket
            return vp.match(parser);
        }

        else { // case b
            parser.backup(m); // undo first vertex name
            return false;
        }
    }

    bool match_edge(Parser& parser,
                    VN& src,
                    VN& dst,
                    EP& ep) {
        int m = 0;

        m  = parser.match_int (src);
        m += parser.match_char(">");
        m += parser.match_int (dst);

        if (m == 3) {
            return ep.match(parser);
        }
        parser.backup(m);
        return false;
    }


protected:

    graph_t graph;
    boost::unordered_map<VN,vertex_t> vertex_from_name;
    boost::unordered_map<vertex_t,VN> name_from_vertex;
};

template < typename VP1, typename EP1, typename VN1 >
std::ostream& operator<<( std::ostream& os,
                          Graph<VP1,EP1,VN1>& g ) {
    return g.print(os);
}

template < typename VP2, typename EP2, typename VN2 >
std::istream& operator>>( std::istream& is,
                          Graph<VP2,EP2,VN2>& g ) {
    return g.read(is);
}

#endif
